#define _CRT_SECURE_NO_WARNINGS 1

 struct ListNode {
    int val;
    struct ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
    
};

 class Solution {
public:

    ListNode* reverse(ListNode* head)
    {
        ListNode* prev = nullptr;
        while (head)
        {
            ListNode* next = head->next;
            head->next = prev;
            prev = head;
            head = next;
        }
        return prev;
    }

    ListNode* addInList(ListNode* head1, ListNode* head2)
    {
        // write code here
        head1 = reverse(head1);
        head2 = reverse(head2);
        ListNode* newhead = new ListNode(-1);
        ListNode* newtail = newhead;


        int sum = 0;
        while (head1 || head2 || sum)
        {
            if (head1)
            {
                sum += head1->val;
                head1 = head1->next;
            }

            if (head2)
            {
                sum += head2->val;
                head2 = head2->next;
            }

            ListNode* tmp = new ListNode(sum % 10);
            sum /= 10;

            newtail->next = tmp;
            newtail = newtail->next;
        }
        return reverse(newhead->next);
    }
};